Understanding the Heap Structure
Heaps are specialized binary tree structures optimized for efficient access to the maximum (or minimum) element, making them the standard implementation for Priority Queues. A Heap is characterized by two mandatory properties:
- Shape Property (Completeness): A heap must be a Complete Binary Tree. This means all levels, except possibly the last, are fully filled, and nodes in the last level are as far left as possible.
- Max-Heap Property (Ordering): The value of every node must be greater than or equal to the values of its children. This ensures the largest element is always found at the root (index 0).
Due to the Shape Property, a heap with $N$ nodes always has a height $H = \Theta(\log N)$, guaranteeing fast operations.
Array-Based Indexing Efficiency
The completeness of the heap allows for an exceptionally space-efficient implementation using a standard 0-indexed array A. We use simple arithmetic to find a node's children or parent, eliminating the need for explicit pointers.
Given a node at index $i$:
| Relationship | Array Index Formula | Example (i=1) |
|---|---|---|
| Parent | $\lfloor (i - 1) / 2 \rfloor$ | $\lfloor (1 - 1) / 2 \rfloor = 0$ |
| Left Child | $2i + 1$ | $2(1) + 1 = 3$ |
| Right Child | $2i + 2$ | $2(1) + 2 = 4$ |
This direct calculation is the basis for key heap algorithms like Heapify.
Heaps vs. BSTs: The Vertical Constraint
- Ordering: A Max-Heap only cares that Parent $\ge$ Children. Unlike BSTs, a Max-Heap allows the right child to be greater than the left child (e.g., Parent=10, Left=3, Right=8 is valid). This relaxed ordering speeds up restructuring.
- Cache Locality: Since array indices are contiguous, accessing related nodes (parent/child) often involves nearby memory locations. This improves cache locality, making array-based heap operations faster in practice than pointer-based BST operations.
- Array Constraint: When implementing heap operations (like insertion or removal), we must take care never to violate the Shape Property—the array must remain compact and fully filled from the start.
1. If a node is at array index $i=5$ in a 0-indexed Max-Heap, which index corresponds to its Left Child?
2. Using the same 0-indexed array, what is the index of the Parent of the node at $i=5$?
3. Which of the following statements is required for a Max-Heap?
4. In a non-empty Max-Heap, where is the largest element always located?